/*
Date:20210524 12:40PM
key:提前存好k个以后的节点，把k个反转并切割出来再合并在已知链表上。不足k个直接拼接
 */
class Solution {
public:
    //反转k个并返回这k个的头
    ListNode* reverse(ListNode* head, ListNode* &new_head,int&count,int&k) 
    {
        if(count<k)
        {
            count++;
            ListNode*last=reverse(head->next,new_head,count,k);
            last->next=head;
            head->next=nullptr;
            return head;
        }
        else
        {
            new_head=head;
            return head;
        }
    }
    //下k个节点
    ListNode* nextk(ListNode* p1,int k)
    {ListNode* p=p1;
    //k=k-1;
        while(k--)
        {
            if(p==nullptr){return nullptr;}
            p=p->next;
        }
        return p;
    }
    //打印
    void print(ListNode* &head)
    {
        ListNode* p=head;
        while(p!=nullptr)
        {
            cout<<p->val<<" ";
            p=p->next;
        }
        cout<<"\n";
    }
    //a接b
    void merge(ListNode* &head,ListNode* &head2)
    {
        if(head2==nullptr){return;}
        if(head==nullptr){head=head2;return;}
        ListNode*p=head;
        while(p->next!=nullptr)
        {
            p=p->next;
        }
        p->next=head2;
    }
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(k==1){return head;}
        //如果后面还有k个
        ListNode*p=head;
        ListNode*fihead=nullptr;
        //这里是跳过k个，所以如果剩下恰好是k个，nextk也会返回null，因此判断k-1符不符合
        while(nextk(p,k-1)!=nullptr)
        {
        //必须提前保留前进k个的节点
        ListNode*p1=nextk(p,k);
        
        int count=1;
        ListNode* new_head;
        //这里会改变p的结构,从p开始反转k个，新链表叫new_head
        reverse(p,new_head, count,k);
        //a后面接b
        {merge(fihead,new_head);}
        
        //p前进k个
        p=p1;
        
        }
        
        //剩下不足k的要合并
        merge(fihead,p);
        return fihead;
    }
};